package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/14 11:56 下午
 */
public class 剑指_Offer_46_把数字翻译成字符串 {

    /**
     * 动态规划
     * 状态转移方程：
     * dp[i] = dp[i-1] + dp[i-2]    num[i-1]*10 + num[i] >= 10 && num[i-1]*10 + num[i] <= 25
     * dp[i] = dp[i-1]              num[i-1]*10 + num[i] < 10 || num[i-1]*10 + num[i] > 25
     * @param num
     * @return
     */
    public int translateNum(int num) {
        String numStr = String.valueOf(num);
        int len = numStr.length();
        if (len < 2) {
            return len;
        }
        int[] dp = new int[len];
        dp[0] = 1;
        Integer tag = Integer.valueOf(numStr.substring(0, 2));
        if (tag >= 10 && tag <= 25) {
            dp[1] = 2;
        } else {
            dp[1] = 1;
        }
        for (int i = 2; i < len; i++) {
            tag = Integer.valueOf(numStr.substring(i-1, i+1));
            if (tag >= 10 && tag <= 25) {
                dp[i] = dp[i-1] + dp[i-2];
            } else {
                dp[i] = dp[i-1];
            }
        }
        return dp[len-1];
    }
}
